package com.ln.leetcode._4;


/**
 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

 算法的时间复杂度应该为 O(log (m+n)) 。


 示例 1：

 输入：nums1 = [1,3], nums2 = [2]
 输出：2.00000
 解释：合并数组 = [1,2,3] ，中位数 2
 示例 2：

 输入：nums1 = [1,2], nums2 = [3,4]
 输出：2.50000
 解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5


 提示：

 nums1.length == m
 nums2.length == n
 0 <= m <= 1000
 0 <= n <= 1000
 1 <= m + n <= 2000
 -106 <= nums1[i], nums2[i] <= 106

 */
public class Solution {

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int size = nums1.length + nums2.length;
        // 中位数下标
        int middle1 = size / 2;
        int middle2 = middle1;
        if(size % 2 == 0) {
            middle1 = middle2 - 1;
        }

        int middle1Val = 0, middle2Val = 0;

        int i = 0, j = 0;
        while (i + j <= middle2) {
            int index = i + j;
            int val;
            if (i >= nums1.length) {
                val = nums2[j++];
            } else if (j >= nums2.length) {
                val = nums1[i++];
            } else {
                if(nums1[i] <= nums2[j]) {
                    val = nums1[i];
                    ++i;
                } else {
                    val = nums2[j];
                    ++j;
                }
            }

            if(index == middle1) {
                middle1Val = val;
            }
            if(index == middle2) {
                middle2Val = val;
            }
        }

        return ((double) middle1Val + (double) middle2Val) / 2;

    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(
            s.findMedianSortedArrays(new int[]{1, 3}, new int[]{2})
        );

        System.out.println(
                s.findMedianSortedArrays(new int[]{1, 2}, new int[]{3, 4})
        );
    }


}
